package asruby.lang
{

    public class SymbolTable {
        static int DEFAULT_INITIAL_CAPACITY = 2048; // *must* be power of 2!
        static int MAXIMUM_CAPACITY = 1 << 30;
        static float DEFAULT_LOAD_FACTOR = 0.75f;
        
        private  var tableLock: ReentrantLock =  new ReentrantLock();
        private  var symbolTable:Array;
        private  var size:int;
        private  var threshold:int;
        private  var loadFactor:float;
        private  var runtime:Ruby;
        
        public  function SymbolTable(runtime:Ruby){
            this.runtime = runtime;
            this.loadFactor = DEFAULT_LOAD_FACTOR;
            this.threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
            this.symbolTable = new SymbolEntry[DEFAULT_INITIAL_CAPACITY];
        }
        
        // note all fields are -- rehash creates new entries when necessary.
        // as documented in java.util.concurrent.ConcurrentHashMap.java, that will
        // statistically affect only a small percentage (< 20%) of entries for a given rehash.
        static class SymbolEntry {
            var hash:int;
            var name:String;
            var symbol:RubySymbol;
            var next:SymbolEntry;
            
            function SymbolEntry(hash:int, name:String, symbol:RubySymbol, next:SymbolEntry){
                this.hash = hash;
                this.name = name;
                this.symbol = symbol;
                this.next = next;
            }
        }

        public  function getSymbol(name:String):RubySymbol{
            var hash: int =  name.hashCode();
            var table:Array;
            for ( var SymbolEntry:e = (table = symbolTable)[hash & (table.length - 1)]; e != null; e = e.next) {
                if (hash == e.hash && name.equals(e.name)) {
                    return e.symbol;
                }
            }
            var lock:ReentrantLock;
            (lock = tableLock).lock();
            try {
                var potentialNewSize:int;
                if ((potentialNewSize = size + 1) > threshold) {
                    table = rehash(); 
                } else {
                    table = symbolTable;
                }
                var index:int;
                // try lookup again under lock
                for ( var SymbolEntry:e = table[index = hash & (table.length - 1)]; e != null; e = e.next) {
                    if (hash == e.hash && name.equals(e.name)) {
                        return e.symbol;
                    }
                }
                var internedName:String;
                var symbol: RubySymbol =  new RubySymbol(runtime, internedName = name.intern());
                table[index] = new SymbolEntry(hash, internedName, symbol, table[index]);
                size = potentialNewSize;
                // write-volatile
                symbolTable = table;
                return symbol;
            } finally {
                lock.unlock();
            }
        }
        
        public  function fastGetSymbol(internedName:String):RubySymbol{
            var internedName: assert = = internedName.intern() : internedName + " is not interned";
            var table:Array;
            for ( var SymbolEntry:e = (table = symbolTable)[internedName.hashCode() & (table.length - 1)]; e != null; e = e.next) {
                if (internedName == e.name) {
                    return e.symbol;
                }
            }
            var lock:ReentrantLock;
            (lock = tableLock).lock();
            try {
                var potentialNewSize:int;
                if ((potentialNewSize = size + 1) > threshold) {
                    table = rehash();
                } else {
                    table = symbolTable;
                }
                var index:int;
                var hash:int;
                // try lookup again under lock
                for ( var SymbolEntry:e = table[index = (hash = internedName.hashCode()) & (table.length - 1)]; e != null; e = e.next) {
                    if (internedName == e.name) {
                        return e.symbol;
                    }
                }
                var symbol: RubySymbol =  new RubySymbol(runtime, internedName);
                table[index] = new SymbolEntry(hash, internedName, symbol, table[index]);
                size = potentialNewSize;
                // write-volatile
                symbolTable = table;
                return symbol;
            } finally {
                lock.unlock();
            }
        }
        
        // backwards-compatibility, but threadsafe now
        public  function lookup(name:String):RubySymbol{
            var hash: int =  name.hashCode();
            var table:Array;
            for ( var SymbolEntry:e = (table = symbolTable)[hash & (table.length - 1)]; e != null; e = e.next) {
                if (hash == e.hash && name.equals(e.name)) {
                    return e.symbol;
                }
            }
            return null;
        }
        
        public  function lookup(id:Number):RubySymbol{
            var table: Array =  symbolTable;
            for ( var int:i = table.length; --i >= 0; ) {
                for ( var SymbolEntry:e = table[i]; e != null; e = e.next) {
                    if (id == e.symbol.id) {
                        return e.symbol;
                    }
                }
            }
            return null;
        }
        
        public  function all_symbols():RubyArray{
            var table: Array =  this.symbolTable;
            var array: RubyArray =  runtime.newArray(this.size);
            for ( var int:i = table.length; --i >= 0; ) {
                for ( var SymbolEntry:e = table[i]; e != null; e = e.next) {
                    array.append(e.symbol);
                }
            }
            return array;
        }
        
        // not so backwards-compatible here, but no one should have been
        // calling this anyway.
        public  function store(symbol:RubySymbol):void{
            throw new UnsupportedOperationException();
        }
        
        private  function rehash():Array{
            var oldTable: Array =  symbolTable;
            var oldCapacity:int;
            if ((oldCapacity = oldTable.length) >= MAXIMUM_CAPACITY) {
                return oldTable;
            }
            
            var newCapacity: int =  oldCapacity << 1;
            var newTable: Array =  new SymbolEntry[newCapacity];
            threshold = (int)(newCapacity * loadFactor);
            var sizeMask: int =  newCapacity - 1;
            var e:SymbolEntry;
            for ( var int:i = oldCapacity; --i >= 0; ) {
                // We need to guarantee that any existing reads of old Map can
                //  proceed. So we cannot yet null out each bin.
                e = oldTable[i];

                if (e != null) {
                    var next: SymbolEntry =  e.next;
                    var idx: int =  e.hash & sizeMask;

                    //  Single node on list
                    if (next == null)
                        newTable[idx] = e;

                    else {
                        // Reuse trailing consecutive sequence at same slot
                        var lastRun: SymbolEntry =  e;
                        var lastIdx: int =  idx;
                        for ( var SymbolEntry:last = next;
                             last != null;
                             last = last.next) {
                            var k: int =  last.hash & sizeMask;
                            if (k != lastIdx) {
                                lastIdx = k;
                                lastRun = last;
                            }
                        }
                        newTable[lastIdx] = lastRun;

                        // Clone all remaining nodes
                        for ( var SymbolEntry:p = e; p != lastRun; p = p.next) {
                            var k: int =  p.hash & sizeMask;
                            var n: SymbolEntry =  newTable[k];
                            newTable[k] = new SymbolEntry(p.hash, p.name, p.symbol, n);
                        }
                    }
                }
            }
            symbolTable = newTable;
            return newTable;
        }
        
    }
}